1. Field of the Invention
The present invention relates to a packet switching network. More particularly, it relates to a packet switching device having a queuing system and a packet scheduler that together handle the traffic control and bandwidth management to support guaranteed quality of service.
2. Related Background Art
IP based networks have evolved from supporting traditional best effort, data centric services to support multiple service grades, multi-media networking services. There is an increased need for the packet-based networks to provide guaranteed quality of service. Providing guaranteed quality of service in packet-based networks requires the use of a packet scheduling system consisting of a queuing system and a packet scheduler. The queuing system allows different traffic streams to receive different service-quality treatments from the scheduler. There are many different kinds of scheduling systems today that support different flavors of quality of service. A desirable scheduling system has the following attributes, which are also indicators for quality of service (Quality of Servicexe2x80x9d):
(1) xe2x80x9cBandwidth Utilizationxe2x80x9d. The scheduling system must utilize bandwidth efficiently;
(2) xe2x80x9cTraffic Flows Isolationxe2x80x9d. Each traffic flow is isolated from the undesirable effect of other flows;
(3) xe2x80x9cScalabilityxe2x80x9d. The scheduling system must support large number of traffic flows;
(4) xe2x80x9cReal-time Priorityxe2x80x9d. Traffic flows with higher real time requirements should be forwarded before traffic flows with lower real time requirements; and
(5) xe2x80x9cFairnessxe2x80x9d. Priority and fairness are conflicting factors, yet a good scheduling system achieves a balance between Fairness and Priority.
Existing scheduling systems may be strong in one or more of the above five aspects, but none has been perfect in all five aspects. Round robin based scheduler has good fairness property, but lacks real-time priority, and the bandwidth utilization is potentially poor. Yet a simple priority based scheduler does not provide fairness, which will result in starvation. There are scheduling algorithms that address Bandwidth Efficiency, Flow Isolation, Fairness and Scalability such as Weighted Fair Queuing, Weighted Round Robin, Frame-Based Fair Queuing, and Starting Potential-Based Fair Queuing. But these algorithms do not address real-time support and neither do they provide flexibility in sharing excess bandwidth.
There are a few algorithms that address Real-Time support, along with Bandwidth Efficiency, Flow Isolation, Fairness and Scalability. Class Based Queuing is one of such algorithms. However, the issues of sharing available bandwidth are still not addressed. Class Based Queuing takes a hierarchical scheduling approach to provide a traffic control mechanism using Weighted Fair Queuing or Weighted Round Robin for guaranteed resource sharing on the base level. On a second level, it groups the flows into different priority categories, so that the flows queues with the highest priority are always considered first to be provided for bandwidth. This priority is important for a networking device to support multiple streams of data with different real time requirements such as voice, interactive data, and file transfer.
For example, U.S. Pat. No., 5,838,686 presents a scarce source allocating system as shown in FIG. 14 and FIG. 15 that can well illustrate Class Based Queuing. As illustrated by the block diagram of a multiplexer system in FIG. 14, all signal paths are illustrated as single signal lines which however could carry multibit digital signals, either in parallel, in which case the signal paths would be composed of multiple signal lines, or serially, in which case the signal paths could be a single data line and/or include a data and clock signal line. A plurality of input terminals 5 are coupled to sources (not shown) of video signals (CHANNEL 1-CHANNEL K) which are to be transmitted together over a data link. The plurality of input terminals 5 are coupled to respective data input terminals of a plurality of corresponding channel processors 10. Respective data output terminals of the plurality of channel processors 10 are coupled to corresponding data input terminals 1-K of a multiplexer (MUX) 20. A data output terminal of the multiplexer 20 is coupled to an output terminal 15 of the multiplexer system. Output terminal 15 is coupled to utilization circuitry (not shown) for transmitting the multiplexed data stream over the transmission link.
Each of the plurality of channel processors 10 further includes a complexity output terminal and a control input terminal. The respective complexity output terminals of each of the plurality of channel processors are coupled to corresponding complexity input terminals of a bit rate allocator 30, and respective quota output terminals of the bit rate allocator 30 are coupled to the corresponding control input terminals of the plurality of channel processors 10.
In operation, each channel processor receives a signal at its control input terminal representing the bit rate allocated to it for the next quota period. The channel processor then encodes the signal at its data input terminal for the next quota period into a digitally encoded signal at the allocated bit rate. The encoded data signal is supplied to the corresponding input terminal of the multiplexer 20. The multiplexer 20 operates in a known manner to combine the signals from all the channel processors into a multiplexed data stream. The multiplexed data stream is then supplied to the circuitry comprising the data link for transmission, also in a known manner.
During the encoding process, the channel processor 10 generates a signal at its complexity output terminal representing the coding complexity of the signal being encoded. The bit rate allocator 30 receives the signals from the complexity output terminals of the channel processors 10, and, based on all of the complexity signals, dynamically adjusts the bit rate quotas for the next quota period among the plurality of channel processors 10. More complex signals are dynamically allocated at a relatively higher bit rate than less complex signals. Different methods of determining the complexity of the video signal and for allocating bit rates based on the complexities are described below.
FIG. 15 is a block diagram of a channel processor which may be used in the multiplexer system illustrated in FIG. 14. In FIG. 15, elements similar to those in FIG. 14 are designated by the same reference number. In FIG. 15, a data input terminal 5 is coupled to a video signal source (not shown). Data input terminal 5 is coupled to a data input terminal of a constant bit rate encoder (CBR) 14, and a complexity analyzer 16. A data output terminal of the CBR encoder 14 is coupled to an input terminal of the multiplexer (MUX) 20 (of FIG. 14). A control input terminal (CONTROL) of the channel processor 10 is coupled to a quota input terminal Q of the CBR encoder 10. An output terminal of the complexity analyzer 16 is coupled to the complexity output terminal (COMPLEXITY) of the channel processor 10.
In operation, the complexity analyzer 16 analyzes the complexity of the video signal at the data input terminal 5. A signal is produced at the output terminal of the complexity analyzer 16 representative of the complexity of the input signal. The complexity representative signal is supplied to the bit rate allocator 30 (of FIG. 14). In response to this complexity signal (and those of the other channel processors 10), the bit rate allocator 30 provides a signal to the control input terminal (CONTROL) of this channel processor 10 (and the other channel processors 10) representing the bit rate allocated to this channel processor 10. The CBR encoder 14 is an encoder which compresses and encodes a video signal in accordance with a standard promulgated by the Moving Picture Expert Group (MPEG), termed an MPEG encoder. The CBR encoder 14 provides a data path between its data input and data output terminals for producing an output signal encoded at a constant bit rate. The constant bit rate is set in response to the signal at the quota input terminal Q from the control input terminal (CONTROL) of the channel processor 10 from the bit rate allocator 30.
Although Class Based Queuing provides better quality of service support, it nevertheless has limitations in its application. First, since Class Based Queuing scheduling is using a hierarchical link-sharing model, real-time priority is supported by addition of a scheduling layer on top of the leaf, this may introduce efficiency trade off. Further, it is difficult to separate out the excess bandwidth sharing from resource reservation. This limits the flexibility of excess bandwidth sharing. The excess bandwidth sharing is a desirable feature in today""s packet based network, in that most of the existing network applications still assume best effort based network services. It is not practical for a File Transfer session to estimate it""s bandwidth requirement and make a claim for it. The more practical approach is to allocate a portion of bandwidth to be shared by sessions such as File Transfer which need not reserve a fixed portion of bandwidth, and assigned a priority level for each session sharing the preserved bandwidth.
Secondarily, Class Based Queuing regulates user traffic only when the out going link is congested. In the hierarchical link-sharing model, since the lower level nodes do not have actual knowledge of the overall load on the outgoing link, they have to rely on approximations for link sharing guideline. This results in additional computational overhead, inefficiency in resource utilization, or unfairness.
The present invention is motivated by the interest in finding out alternative solutions to offer the desired Quality of Service features previously described.
The present invention relates to a switching device in a packet switching network. The switching device takes a number of input packet flows and transmit them to the outgoing link. Since the capacity of the outgoing link may not always be able to transmit all the input packet flows at the same time, the switching device need to queue the input packet flows and schedule them to be feed to the outgoing link. The quality of service of the switching network is then depend on how the switching device handle the packet flows to best utilize the resources to transmit all the packet flows with speed and quality. The switching device has a queuing system and a packet scheduler, that are handling the queuing and scheduling respectively. Their performance is thus key to the improvement of the network""s quality of service.
The present invention provides an innovated packet scheduling system for a packet switching device to better support the quality of service. The packet scheduling system consists of a queuing system, which isolates the input packet flow from one another and a scheduling system named packet scheduler, which runs a scheduling algorithm to allocate bandwidth to the packet flows. One aspect of the present invention is to define a set of service parameters for each flow to indicate different aspects of the quality of service and consumption of resource. These parameters are defined as follows: (1) xe2x80x9cReal Time Priorityxe2x80x9d shall mean that the packets in a higher real time priority traffic flow are processed earlier than the packets in a lower real time priority traffic flow; (2) xe2x80x9cReserved Bandwidthxe2x80x9d shall mean that the bandwidth committed by the scheduling system to the traffic flow; and (3) xe2x80x9cExcess Bandwidth Priorityxe2x80x9d shall mean a weighting factor for the traffic flow in sharing the excess bandwidth.
Another aspect of the present invention is to use multiple First-In-First-Out packet queues in the queuing system to meet potentially different Quality of Service requirements for different traffic flows. A traffic flow is referred to as a stream of packets that receives the same forwarding treatment by the network. It can be a voice session between two parties, or a file transfer session between a client and file server, or an aggregated stream of multiple sessions between two networks. Each packet queue, or flow queue, is associated with one or more traffic flows. The following set of parameters are attributed to each packet queue according to the invention: (1) xe2x80x9cMaximum Reserved Bandwidth Creditxe2x80x9d or xe2x80x9cMRBCxe2x80x9d shall correspond to the flow queue""s share of reserved bandwidth; (2) xe2x80x9cAvailable Reserved Bandwidth Creditxe2x80x9d or xe2x80x9cARBCxe2x80x9d shall mean an auxiliary variable for a flow queue used to keep track of the traffic flow""s bandwidth usage and a non-empty flow queues with positive ARBC is ready to be processed by the scheduler; (3) xe2x80x9cMaximum Excess Bandwidth Creditxe2x80x9d or xe2x80x9cMEBCxe2x80x9d shall correspond to the flow queue""s share of excess bandwidth; (4) xe2x80x9cAvailable Reserved Bandwidth Creditxe2x80x9d or xe2x80x9cARBCxe2x80x9d shall mean an auxiliary variable for each flow queue used to keep track of a traffic flow""s excess bandwidth usage in that a non-empty flow queues with positive AEBC is ready to be processed by the scheduler; and (5) xe2x80x9cReal Time Priorityxe2x80x9d shall decide among that backlogged flow queues with available bandwidth credit, which flow queue is processed first.
Yet another aspect of the present invention is to use a dual-frame approach in the packet scheduler to allocate reserved bandwidth and excess bandwidth for each flow queue. In this approach, the time domain is divided into recurring fixed size Synchronous Frames; concatenating discrete portions of contiguous Synchronous Frames forms the Asynchronous Frames. Synchronous Frame is accessed by transmitting packets from a backlogged flow queue using the flow queue""s ARBC, and Asynchronous Frame is accessed by transmitting packets from a backlogged flow queue using the flow queue""s AEBC. To allocate reserved bandwidth, each traffic flow""s ARBC is initialized to its MRBC at the beginning of a Synchronous Frame. When a packet is transmitted from a backlogged flow queue using the flow queue""s reserved bandwidth, its ARBC is subtracted an amount proportional to the packet size. A flow queue with negative ARBC is not eligible for Synchronous Frame Access. The packet scheduler uses a sorted priority queue, the Synchronous Priority Queue (SPQ), to maintain those backlogged flow queues with positive ARBC. The SPQ is sorted in decreasing order of real time priority. When a flow queue with positive ARBC becomes backlogged, it is put in the SPQ, and when a flow queue in the SPQ consumed all its ARBC or becomes empty, it is removed from the SPQ.
To control the Synchronous Frame, a routine is executed at each clock tic, which increment its internal count each time. When its internal count reaches the count for the size of the Synchronous Frame, the end of a Synchronous Frame is detected, and its internal tic count is reset to zero. At the beginning of every Synchronous Frame, all the packet queues"" available reserved bandwidth credits are compensated up to their MAC. After the compensation, if a non-empty packet queue has positive ARBC and is not in the SPQ is put back to the SPQ.
In dealing with excess bandwidth allocation, each traffic flow""s share of excess bandwidth is translated into its MEBC in a Asynchronous Frame period, and its AEBC corresponds to its available excess bandwidth in that Asynchronous Frame Period.
The packet scheduler accesses the Asynchronous Frame by transmitting packets from a backlogged flow queue using the flow queue""s share of excess bandwidth. During the Asynchronous Frame access, each time a packet is transmitted from a flow queue, the flow queue""s AEBC is subtracted an amount proportional to the packet size. A flow queue with negative AEBC is not eligible for Asynchronous Frame Access. The packet scheduler uses a sorted priority queue, the Asynchronous Priority Queue (APQ), to keep those backlogged flow queues with positive AEBC. The APQ is sorted in decreasing order of real time priority. When a flow queue with positive AEBC becomes backlogged, it is put in the APQ, and when a flow queue in the APQ consumed all its AEBC or becomes empty, it is removed from the APQ.
The Asynchronous Frame restarts when no backlogged priority queue has positive AEBC. Every time an Asynchronous Frame restarts, each flow queue is compensated up to its MEBC worth of AEBC. After the compensation, if a nonempty packet queue has positive AEBC and is not in the APQ is put back to the APQ.
The Synchronous Frame Access always has a priority than Asynchronous Frame Access. The packet scheduler continues to access the SPQ until the SPQ becomes empty, then the packet scheduler begins to access the APQ. After a packet is transmitted from a flow queue in the APQ, the packet scheduler immediately switches over to the SPQ if the SPQ is not empty.
The uses of SPQ and APQ are to support real time priority for each traffic flow. An alternative design to support real time priority is to use a Priority Control Block, which is an array of entries indexed by the real time priority. Each entry in the array contains two FIFO queues: the Synchronous Access Queue, which contains a list of backlogged flow queues with positive ARBC, and the Asynchronous Access Queue, which contains a list of backlogged flow queue with positive AEBC. A backlogged flow queue is put in the queues of the entry indexed by the flow queue""s real timer priority. A bit mapped array can be used to keep track of the PCP entries containing non-empty queues. Since the PCB is implicitly sorted, the packet scheduler only needs to go to the entry corresponding to the location of the first bit in the bit mapped array that is set.